// easy

// 给定A,B两个链表，判断两个链表是否相交，返回相交的起始点，如果不相交，则返回null

// 思路： 将链表A的末尾拼接上链表B，链表B的末尾拼接上链表A,然后使用两个指针pA，pB，分别从链表A，链表B的头节点开始遍历，如果走到共同的节点，则返回该节点
// 否则走到两个链表末尾，返回null

// 时间复杂度：O(m+n)
// 空间复杂度：O(1)
const {ListNode, LinkedList} = require('../../1. 链表基础/1. 建立线性链表')
function getIntersectionNode(headA, headB) {
    if (headA === null || headB === null) {
    return null
    }
    let pA = headA
    let pB = headB
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return pA
}

let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node1.next = node2
node2.next = node3
node3.next = node4


let node11 = new ListNode(22)
let node22 = new ListNode(55)
let node33 = new ListNode(11)
let node44 = new ListNode(77)
node11.next = node22
node22.next = node33
node33.next = node44
// node44.next = node4

console.log(getIntersectionNode(node1, node11))